package org.example;

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int[][] dp = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = 1;   //以nums[i]为结尾的最长序列个数
            dp[i][1] = 1;   //以nums[i]为结尾的最长序列长度
        }

        for (int i = 1; i < nums.length; i++) {
            int maxLen = 1;
            int maxCount = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j][1] + 1 > maxLen) {
                        maxLen = dp[j][1] + 1;
                        maxCount = dp[j][0];
                    } else if (dp[j][1] + 1 == maxLen) {
                        maxCount += dp[j][0];
                    }
                }
            }
            dp[i][0] = maxCount;
            dp[i][1] = maxLen;
        }
        //for (int[] each : dp) {
        //    System.out.println(Arrays.toString(each));
        //}

        int maxCount = 1;
        int maxLen = 1;
        for (int i = 1; i < nums.length; i++) {
            if (dp[i][1] > maxLen) {
                maxLen = dp[i][1];
                maxCount = dp[i][0];
            } else if (dp[i][1] == maxLen) {
                maxCount += dp[i][0];
            }
        }
        return maxCount;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}